#include <bits/stdc++.h>

using namespace std;

class Solution{
public:
    vector<string> stringSeq(string target){
        string s; vector<string> ret;
        for(char c: target){
            s+='a';
            ret.push_back(s);
            while(s.back()<c)
                ++s.back(), ret.push_back(s);
        } return ret;
    }
};

class Solution2{
public:
    int numberOfSubstring(string s, int K){
        int n=s.size(), ans=0;
        for(int i=0;i<n;i++){
            int cnt[26]={0};
            int mx=0;
            for(int j=i;j<n;j++){
                int t=++cnt[s[j]-'a'];
                mx=max(mx,t);
                if(mx>=K) ans++;
            }
        } return ans;
    }
};

const int N=1e6; bool inited=false; int A[N+10];
void init(){
    if(inited) return; inited=true;
    memset(A,0,sizeof(A));
    A[1]=1;
    for(int i=2;i<=N;i++)
        if(A[i]==0)
            for(int j=i;j<=N;j+=i)
                if(A[j]==0) A[j]=i;
}
class Solution3{
public:
    int minOpe(vector<int>& nums){
        init();
        int n=nums.size();
        auto get=[&](int x,int j){return j==0?x:A[x];};
        const int INF=1e9;
        int f[n][2];
        for(int i=0;i<n;i++) f[i][0]=f[i][1]=INF;
        f[0][0]=0;f[0][1]=1;
        for(int i=1;i<n;i++) for(int j=0;j<2;j++) for(int jj=0;jj<2;jj++){
            int x=get(nums[i],j), y=get(nums[i-1],jj);
            if(x>=y) f[i][j]=min(f[i][j],f[i-1][jj]+j);
        }
        int ans=min(f[n-1][0], f[n-1][1]);
        return ans<INF?ans:-1;
    }
};

// 4
#define ll long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rnd(int x, int y) {
    return uniform_int_distribution<int>(x, y)(rng);
}

long long MOD = 1e18 + rnd(0, 1e9);
long long BASE = 233 + rnd(0, 1e3);

struct HashSeq {
    vector<__int128> P, H;

    HashSeq(string &s) {
        int n = s.size();
        P.resize(n + 1);
        P[0] = 1;
        for (int i = 1; i <= n; i++) P[i] = P[i - 1] * BASE % MOD;
        H.resize(n + 1);
        H[0] = 0;
        for (int i = 1; i <= n; i++) H[i] = (H[i - 1] * BASE + s[i - 1]) % MOD;
    }

    long long query(int l, int r) {
        return (H[r] - H[l - 1] * P[r - l + 1] % MOD + MOD) % MOD;
    }
};
class Solution4{
public:
    vector<bool> findAns(vector<int>& parent, string s){
        int n=parent.size(); vector<int> e[n];
        for(int i=1;i<n;i++) e[parent[i]].push_back(i);
        vector<pair<int,int>> vec(n);
        string t;
        function<void(int sn)> dfs=[&](int sn)->void{
            int l=t.size()+1;
            for(int fn:e[sn]) dfs(fn);
            t.push_back(s[sn]);
            int r=t.size();
            vec[sn]={l,r};
        };
        dfs(0);
        HashSeq hs(t);
        reverse(t.begin(), t.end()); HashSeq hr(t); vector<bool> ans;
        for(int i=0;i<n;i++){
            int l=vec[i].first,r=vec[i].second,len=r-l+1;
            ll v1=hs.query(l,l+len/2-1);
            ll v2=hr.query(n+1-r,n+1-r+len/2-1);
            ans.push_back(v1==v2);
        }
        return ans;
    }
};

int main(){
    Solution s; vector<string> ans1=s.stringSeq("abc"); for(auto x: ans1) cout<<x<<" "; cout<<endl;
    Solution2 s2; cout<<s2.numberOfSubstring("abacb",2)<<endl;
    vector<int> nums3={25,7};
    Solution3 s3; cout<<s3.minOpe(nums3)<<endl;

    vector<int> parent={-1,0,0,1,1,2};
    Solution4 s4; vector<bool> ans4=s4.findAns(parent, "aababa"); for(auto x: ans4) cout<<x<<" "; cout<<endl;
}